package leetcode.D400.T340;

import java.util.HashMap;
import java.util.Map;

class Solution {
//    public int lengthOfLongestSubstringKDistinct(String s, int k) {
//        Map<Character, Integer> map = new HashMap<>();
//        int left = 0, right = 0;
//        int maxLen = 0;
//        while(right < s.length()) {
//            char c = s.charAt(right++);
//            if(map.containsKey(c)) {
//                map.put(c, map.get(c)+1);
//            } else {
//                map.put(c, 1);
//            }
//            if(map.size() <= k) {
//                maxLen = Math.max(maxLen, right-left);
//            }
//            while(map.size() > k) {
//                char d = s.charAt(left++);
//                int origin = map.get(d);
//                if(origin == 1) {
//                    map.remove(d);
//                } else {
//                    map.put(d, origin-1);
//                }
//            }
//        }
//        return maxLen;
//    }

    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(k == 0) {
            return 0;
        }
        int left = 0, right = 0, diff = 0, maxLen = 0;
        Map<Character, Integer> window = new HashMap<>();
        while(right < s.length()) {
            char c = s.charAt(right++);
            int origin = window.getOrDefault(c, 0);
            window.put(c, origin + 1);
            if(origin == 0) {
                diff++;
            }
            if(diff <= k) {
                maxLen = Math.max(maxLen, right-left);
            }
            while(diff > k) {
                char d = s.charAt(left++);
                int originVal = window.get(d);
                window.put(d, originVal-1);
                if(originVal == 1) {
                    diff--;
                }
            }
        }
        return maxLen;
    }
}
